We study the problem of list-decodable linear regression, where an adversary can corrupt a majority of the examples.

The k -sparse parity problem is a classical problem in computational complexity and algorithmic theory, serving as a key benchmark for understanding computational classes. In this paper, we solve the k -sparse parity problem with sign stochastic gradient descent, a variant of stochastic gradient descent (SGD) on two-layer fully-connected neural networks. We demonstrate that this approach can efficiently solve the k -sparse parity problem on a d -dimensional hypercube ( k\le O(\sqrt{d})) with a sample complexity of \tilde{O}(d {k-1}) using 2 {\Theta(k)} neurons, matching the established \Omega(d {k}) lower bounds of Statistical Query (SQ) models. Our theoretical analysis begins by constructing a good neural network capable of correctly solving the k -parity problem. We then demonstrate how a trained neural network with sign SGD can effectively approximate this good network, solving the k -parity problem with small statistical errors.

We study the problem of list-decodable linear regression, where an adversary can corrupt a majority of the examples. Specifically, we are given a set T of labeled examples (x, y) \in \mathbb{R} d \times \mathbb{R} and a parameter 0 \alpha 1/2 such that an \alpha -fraction of the points in T are i.i.d. The goal is to output a small list of hypothesis vectors such that at least one of them is close to the target regression vector. Our main result is a Statistical Query (SQ) lower bound of d {\mathrm{poly}(1/\alpha)} for this problem. Our SQ lower bound qualitatively matches the performance of previously developed algorithms, providing evidence that current upper bounds for this task are nearly best possible.